#include "linearList.h"
#include <iostream>
#include <algorithm>
using namespace std;

sequenceList::sequenceList(const int& capacity, const int& length, float arr[]) {
    maxCapcity = capacity;
    myList = new float[maxCapcity];
    curNumberOfItem = length;
    for (int i = 0; i < length; i++) {
        myList[i] = arr[i];
    }
}

sequenceList::~sequenceList() {
    delete[] myList;
}

bool sequenceList::addItem(const float& item) {
    if (curNumberOfItem >= maxCapcity) return false;
    myList[curNumberOfItem++] = item;
    return true;
}

bool sequenceList::insertItem(const int& index, const float& item) {
    if (index < 0 || index > curNumberOfItem || curNumberOfItem >= maxCapcity) 
        return false;
    for (int i = curNumberOfItem; i > index; i--) {
        myList[i] = myList[i - 1];
    }
    myList[index] = item;
    curNumberOfItem++;
    return true;
}

int sequenceList::deleteItem(const float& item) {
    for (int i = 0; i < curNumberOfItem; i++) {
        if (myList[i] == item) {
            for (int j = i; j < curNumberOfItem - 1; j++) {
                myList[j] = myList[j + 1];
            }
            curNumberOfItem--;
            return i;
        }
    }
    return -1;
}

bool sequenceList::locate(const int& index, float& val) {
    if (index < 0 || index >= curNumberOfItem) return false;
    val = myList[index];
    return true;
}

int sequenceList::locate(const float& item) {
    for (int i = 0; i < curNumberOfItem; i++) {
        if (myList[i] == item) return i;
    }
    return -1;
}

void sequenceList::reverse() {
    for (int i = 0; i < curNumberOfItem / 2; i++) {
        float temp = myList[i];
        myList[i] = myList[curNumberOfItem - 1 - i];
        myList[curNumberOfItem - 1 - i] = temp;
    }
}
//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}

listNode::listNode(float nodeData, listNode* succ) {
    data = nodeData;
    next = succ;
}

listNode::~listNode() {}

linkList::linkList() {
    firstNode = new listNode();
    lastNode = firstNode;
    curNode = firstNode;
    listSize = 0;
}

linkList::linkList(const int& length, float arr[]) {
    firstNode = new listNode();
    lastNode = firstNode;
    curNode = firstNode;
    listSize = 0;
    for (int i = 0; i < length; i++) {
        tailInsertItem(arr[i]);
    }
}

linkList::~linkList() {
    curNode = firstNode;
    while (curNode != nullptr) {
        listNode* temp = curNode;
        curNode = curNode->next;
        delete temp;
    }
}

bool linkList::headInsertItem(const float& item) {
    listNode* newNode = new listNode(item, firstNode->next);
    firstNode->next = newNode;
    if (lastNode == firstNode) {
        lastNode = newNode;
    }
    listSize++;
    return true;
}

bool linkList::tailInsertItem(const float& item) {
    listNode* newNode = new listNode(item);
    lastNode->next = newNode;
    lastNode = newNode;
    listSize++;
    return true;
}

int linkList::insertItem(const int& index, const float& item) {
    if (index < 0 || index > listSize) return -1;
    
    if (index == 0) {
        headInsertItem(item);
        return 0;
    }
    if (index == listSize) {
        tailInsertItem(item);
        return index;
    }
    
    curNode = firstNode;
    for (int i = 0; i < index; i++) {
        curNode = curNode->next;
    }
    listNode* newNode = new listNode(item, curNode->next);
    curNode->next = newNode;
    listSize++;
    return index;
}

int linkList::deleteItem(const float& item) {
    curNode = firstNode;
    int pos = 0;
    while (curNode->next != nullptr) {
        if (curNode->next->data == item) {
            listNode* temp = curNode->next;
            curNode->next = temp->next;
            if (temp == lastNode) {
                lastNode = curNode;
            }
            delete temp;
            listSize--;
            return pos;
        }
        curNode = curNode->next;
        pos++;
    }
    return -1;
}

bool linkList::locate(const int& index, float& val) {
    if (index < 0 || index >= listSize) return false;
    
    curNode = firstNode->next;
    for (int i = 0; i < index; i++) {
        curNode = curNode->next;
    }
    val = curNode->data;
    return true;
}

int linkList::locate(const float& item) {
    curNode = firstNode->next;
    int pos = 0;
    while (curNode != nullptr) {
        if (curNode->data == item) {
            return pos;
        }
        curNode = curNode->next;
        pos++;
    }
    return -1;
}

void linkList::ascendingOrder() {
    if (listSize <= 1) return;

    float* tempArray = new float[listSize];
    curNode = firstNode->next;
    for (int i = 0; i < listSize; i++) {
        tempArray[i] = curNode->data;
        curNode = curNode->next;
    }

    for (int i = 0; i < listSize - 1; i++) {
        for (int j = 0; j < listSize - 1 - i; j++) {
            if (tempArray[j] > tempArray[j + 1]) {
                float temp = tempArray[j];
                tempArray[j] = tempArray[j + 1];
                tempArray[j + 1] = temp;
            }
        }
    }

    curNode = firstNode->next;
    for (int i = 0; i < listSize; i++) {
        curNode->data = tempArray[i];
        curNode = curNode->next;
    }
    
    delete[] tempArray;
}

void linkList::reverse() {
    if (listSize <= 1) return;
    
    listNode* prev = nullptr;
    curNode = firstNode->next;
    lastNode = curNode; 
    
    while (curNode != nullptr) {
        listNode* nextTemp = curNode->next;
        curNode->next = prev;
        prev = curNode;
        curNode = nextTemp;
    }
    
    firstNode->next = prev; 
}

void linkList::print()
{
    cout << listSize << ":";
    
    if (listSize == 0) {
        cout << endl;
        return;
    }
    
    curNode = firstNode;
    while (curNode->next != nullptr) {
        curNode = curNode->next;
        cout << curNode->data;
        if (curNode->next != nullptr) {
            cout << ",";
        } else {
            cout << endl;
        }
    }
}

void merge(linkList& A, linkList& B) {
    A.ascendingOrder();
    B.ascendingOrder();

    listNode* newFirst = new listNode();
    listNode* current = newFirst;
    
    listNode* aNode = A.firstNode->next;
    listNode* bNode = B.firstNode->next;

    while (aNode != nullptr && bNode != nullptr) {
        if (aNode->data <= bNode->data) {
            current->next = aNode;
            aNode = aNode->next;
        } else {
            current->next = bNode;
            bNode = bNode->next;
        }
        current = current->next;
    }

    if (aNode != nullptr) {
        current->next = aNode;
    } else {
        current->next = bNode;
    }

    A.firstNode->next = newFirst->next;

    A.curNode = A.firstNode;
    while (A.curNode->next != nullptr) {
        A.curNode = A.curNode->next;
    }
    A.lastNode = A.curNode;

    A.listSize += B.listSize;

    B.firstNode->next = nullptr;
    B.lastNode = B.firstNode;
    B.listSize = 0;

    delete newFirst;

    A.reverse();
}
